敵対的探索と制約充足

第3回へようこそ： 人工知能の概念（PolyU COMP5511）。今回のセッションでは、単一エージェントの経路探索から 敵対的探索へと移行します。これはエージェントが競争的なマルチエージェント環境で行動するものです。さらに 制約充足問題（CSP）も紹介します。これは経路ではなく、特定の制約条件を満たす状態を見つけることを目的とするパラダイムです。

中核となる概念

• 敵対的探索： インテリジェントな相手に対して合理的な意思決定を行うための ミニマックス法 や アルファ・ベータ枝刈り などのアルゴリズムに焦点を当てます。
• モンテカルロ木探索（MCTS）： 確率的な意思決定を探究し、 AlphaGoのような現代のゲームAIの基盤となっています。
• 制約充足： 変数、ドメイン、制約を用いて問題をモデル化し、 バックトラッキング や 局所探索のような現代のゲームAIの基盤となっています。

計算量の分析

敵対的な設定では、探索空間の計算量はしばしばゲームの分岐因子 $b$ と深さ $d$によって定義され、計算コストは次のようになります： $$O(b^d)$$ この指数的な増大には、アルファ・ベータ枝刈りのような効率的な枝刈り戦略が必要です。